/**
 * https://leetcode.cn/problems/longest-palindromic-substring/submissions/576805315/
 * 5.最长回文子串
 * medium 陈贝纯 10.30
 * 区间dp
 */

class Solution {
public:
    string longestPalindrome(string s) {
        int n=s.length();
        int sum=1;
        int begin=0;
        if(n<2)
        return s;
        vector<vector<bool>>dp(n,vector<bool>(n));
        for(int i=0;i<n;++i){
            dp[i][i]=true;
        }
        for(int L=2;L<=n;++L){
            for(int i=0;i<n;++i){
                int j=L+i-1;
                if(j>=n)
                break;
                if(s[i]!=s[j])
                dp[i][j]=false;
                else{
                    if(j-i<3)
                    dp[i][j]=true;
                    else
                    dp[i][j]=dp[i+1][j-1];
                    if(dp[i][j]&&j-i+1>sum){
                        sum=j-i+1;
                        begin=i;
                    }
                }
            }
        }
        return s.substr(begin,sum);
    }
};